package com.zjj.algorithm.learning.dmsxl.dynamicplan;

/**
 * 对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！
 * <p>
 * 确定dp数组（dp table）以及下标的含义
 * 确定递推公式
 * dp数组如何初始化
 * 确定遍历顺序
 * 举例推导dp数组
 * <p>
 * 一些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？
 * <p>
 * <p>
 * 509. 斐波那契数 简单题
 * 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
 * <p>
 * F(0) = 0，F(1) = 1
 * F(n) = F(n - 1) + F(n - 2)，其中 n > 1
 * 给定 n ，请计算 F(n) 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 2
 * 输出：1
 * 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
 * 示例 2：
 * <p>
 * 输入：n = 3
 * 输出：2
 * 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
 * 示例 3：
 * <p>
 * 输入：n = 4
 * 输出：3
 * 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
 * <p>
 * <p>
 * 提示：
 * <p>
 * 0 <= n <= 30
 *
 * @author zjj_admin
 * @date 2022/12/22 15:43
 */
public class DynamicPlan_02_FibonacciNumber {

    public static void main(String[] args) {
        int res = fib(8);
        System.out.println("res = " + res);
    }

    /**
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     * <p>
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 38.4 MB
     * 击败
     * 28.38%
     *
     * @param n
     * @return
     */
    public static int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int num1 = 1;
        int num2 = 1;
        int num = 0;
        for (int i = 3; i <= n; i++) {
            num = num1 + num2;
            num1 = num2;
            num2 = num;
        }
        return num;
    }
}
